Solving equation systems in omega-categorical algebras

Abstract: We study the computational complexity of deciding whether a given set of term equalities and inequalities has a solution in an omega-categorical algebra $A$. There are omega-categorical groups where this problem is undecidable. We show that if $A$ is an omega-categorical semilattice or an abelian group, then the problem is in P or NP-hard. The hard cases are precisely those where $Pol(A,\neq)$ is ``small'' (has a uniformly continuous minor-preserving map to the clone of projections on a two-element set). We rely on the Barto-Pinsker theorem about the existence of pseudo-Siggers polymorphisms. To the best of our knowledge, this is the first time that the pseudo-Siggers identity has been used to prove a complexity dichotomy.

category theoryrings and algebras

Audience: researchers in the topic

York semigroup seminar

Series comments: Description: Semigroup-related research talks at University of York.

Email Nora Szakacs at nora.szakacs@york.ac.uk for the meeting password.